A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention broadly relates to automatic volume discretization of a geometric object using hexahedral elements, and, more particularly, to a system and method to convert a hex-dominant mesh structure into an all-hex mesh structure using all-hex templates where each template is composed of a family of modular hexahedral sub-templates and where triangular and rectangular patterns can be freely combined on the template""s exterior faces.
2. Description of the Related Art
Finite element analysis is a numerical method that solves mathematical problems in engineering and physics for determining the physical behavior of a geometric object or region. Finite element analysis is used in approximating any continuous physical characteristic or behavior (such as structural mechanics, effect of temperature, pressure, heat, or an electric field, etc.) of a geometric region by a discrete model of a set of piece-wise continuous functions. The geometric region is broken into discrete elements interconnected at discrete node points. Typically, finite element analysis is performed on a computer in a three-step procedure comprising the steps of pre-processing, processing, and post-processing. In the pre-processing step, geometric boundary data representing the geometric region to be analyzed is taken, and a mesh of geometrical elements covering the domain of the geometric region is generated. Thus, mesh generation is the process of discretizing a continuous geometry into small elements for use in the finite element analysis. In the processing step, the element data are taken and mathematical equations are applied to solve for the characteristic of interest across the domain through use of matrix equations. For example, a stimulus is applied to the mesh data and the reaction of the mesh data to the stimulus is analyzed. In the post-processing step, the results of this finite element analysis are output, for example, in a graphical representation of the characteristic of interest.
Traditionally, generating a mesh for a given geometry has been very tedious, time consuming, and error prone. However, with the advent of sophisticated computing machines, the mesh generation process is substantially automated. The automated meshing systems for general three-dimensional (3D) volumes traditionally give tetrahedral- or hexahedral-shaped elements, or a combination of the two types. A mesh is constrained in terms of how elements share subfacets within the mesh. This problem is much less constrained for tetrahedral or mixed element meshes, hence tetrahedral and mixed element meshing algorithms have. received the most attention in the past. However, due to increased- accuracy and efficiency of eight-node hexahedral elements for non-linear structural mechanics and other applications, there is a growing demand for all-hex meshing systems. The discussion hereinbelow refers to a hexahedral element as a xe2x80x9chex.xe2x80x9dFIG. 1 shows a hex-dominant mesh 10 and its constituent elements. A hex-dominant mesh (e.g., the mesh 10) is a three-dimensional mesh that consists of four types of elementsxe2x80x94hexahedral elements (e.g., elements 16 in the mesh 10), prism elements (e.g., elements 18 in the mesh 10), pyramid elements (e.g., elements 12 in the mesh 10) and tetrahedral elements (e.g., elements 14 in the mesh 10)xe2x80x94as illustrated in FIG. 1. An all-hex mesh is a mesh that consists of exclusively hexahedral elements.
Although it would be ideal if an all-hex mesh could be generated for an arbitrary three-dimensional shape without going through a hex-dominant mesh, the direct all-hex meshing problem is known to be highly challenging, and none of the existing methods always succeeds to create a valid all-hex mesh for a complex three-dimensional geometry. A few of such existing methods of all-hex mesh creation are described in the following: (1) Blacker, T. D. and R. J. Meyers, xe2x80x9cSeams and Wedges in Plastering: A 3-D Hexahedral Mesh Generation Algorithm,xe2x80x9d Engineering with Computers, 1993, 2(9), pp. 83-93 (hereinafter, xe2x80x9cMeyersxe2x80x9d); (2) Tautges, T. J., T. Blacker, and S. A. Mitchell, xe2x80x9cThe Whisker Weaving Algorithm: A Connectivity-Based Method for Constructing All-Hexahedral Finite Element Meshesxe2x80x9d, International Journal for Numerical Methods in Engineering, 1996, vol. 39, pp. 3327-3349 (hereafter, xe2x80x9cBlackerxe2x80x9d); and (3) U.S. Pat. No. 5,768,156, issued on Jun. 16, 1998 to Tautges et al. (hereafter, xe2x80x9cTautgesxe2x80x9d). Although there exists a trivial solutionxe2x80x94reating a tetrahedral mesh first and subdividing each of the tetrahedral elements (hereafter, xe2x80x9ctetxe2x80x9d) into four smaller hex elementsxe2x80x94topological and geometric irregularity of such an all-hex mesh is so poor that this method is not used in practice. Creating a quality hex-dominant mesh, on the other hand, is an easier problem, either by hand or by an automated algorithm as described in (1) Owen, S. J., S. A. Canann, and S. Saigal, xe2x80x9cPyramid Elements for Maintaining Tetrahedra to Hexahedra Confornabilityxe2x80x9d, AMD-Vol. 220, Trend in Unstructured Mesh Generation, ASME, 1997, pp. 123-129 (hereafter xe2x80x9cOwenxe2x80x9d); and (2) Owen, S. J. and S. Saigal, xe2x80x9cH-Morph: An Indirect Approach to Advancing Front Hex Meshingxe2x80x9d, International Journal for Numerical Methods in Engineering, 2000, 49, pp. 289-312 (hereafter xe2x80x9cSaigalxe2x80x9d). The disclosures of Owen and Saigal are incorporated herein by reference in their entireties.
In order to highlight the difficulty in developing conversion templates for all-hex meshing, it is important to take a look at a much easier, two-dimensional problem of converting a quad-dominant mesh to an all-quad mesh. FIG. 2 illustrates conversion of a quad-dominant mesh 20 into an all-quad mesh 22. The input quad-dominant mesh 20 includes a number of quadrilaterals (or quads) 21 and triangles 23. FIG. 3 illustrates two types of templates for converting a quad-dominant mesh into an all-quad mesh. The template quadrilateral 30 is shown with its constituent all-quad elements 32, and the, template triangle 34 is shown with its constituent all-quad elements 36. The conversion of the mesh 20 in FIG. 2 is accomplished with only these two types of templates shown in FIG. 3. In FIG. 2, the quad elements for quadrilaterals 21 are depicted by the numeral 25, and the quad elements for triangles 23 are depicted by the numeral 27. With the two types of templates shown in FIG. 3, it is guaranteed that any quad-dominant mesh can be converted to an all-quad mesh.
During this all-quad mesh conversion it is important to maintain the interface conformity, or the topological and geometric conformity between adjacent mesh elements. To maintain the conformity each of the all interior edges of a final mesh must be shared by exactly two elements. By using the two templates shown in FIG. 3, it is trivial to satisfy such conformity in the all-quad mesh conversion because all the edges of an input quad-dominant mesh are always split into two segments.
In the all-hex mesh conversion problem, a similar interface comformity requirement still exists. The common method for converting a hex-dominant mesh into an all-hex mesh is to subdivide, or dice, a non-hex element into a set of smaller hexes. A hex in the original mesh is also subdivided into a set of smaller hexes. However, it is noted that in a final all-hex mesh, all the interfaces between adjacent hexes must be quadrilaterals, and each of the quadrilaterals must be shared by exactly two hexes in order to maintain the conformity.
Despite the apparent similarity of the problem statement, the all-hex mesh conversion problem turns out significantly more challenging than the all-quad mesh conversion problem discussed hereinabove because of the following two reasons: (1) An input hex-dominant mesh consists of four different types of elementsxe2x80x94hexes, prisms, pyramids and tetsxe2x80x94as opposed to only two types as in a quad-dominant mesh; and (2) A hex-dominant mesh has two types of interfacesxe2x80x94triangles and quadrilateralsxe2x80x94which make it more difficult to maintain the topological and geometric conformity at the interfaces, compared with the all-quad mesh conversion problem in which there is only one type of interfacexe2x80x94a line segment.
Among the four types of elements in a hex-dominant mesh, hexes, tets, and prisms have the following well-known, simple conversion templates: (1) A hex element can be split into eight smaller hex elements by adding a node at the center of the volume, six nodes at the centers of six quadrilateral faces, and twelve nodes at the centers of twelve edges of the original hex; (2) A tet element can be split into four smaller hex elements by adding a node at the center of the volume, four nodes at the centers of four triangular faces, and six nodes at the centers of six edges of the original tet; and (3) A prism element can be split into six smaller hex elements by adding a node at the center of the volume, five nodes at the centers of two triangular faces and three quadrilateral faces, and nine nodes at the centers of nine edges of the original prism. It is noted that all of these three templates apply aforementioned all-quad templates shown in FIG. 3xe2x80x94splitting a triangular face of the original element into three smaller quadrilaterals, and a quadrilateral face into four smaller quadrilaterals.
One problem is that there is no such template known for a pyramid. FIG. 4 shows a pyramid element 40 with four triangular faces 42 and one quadrilateral face 44 (not visible) at the bottom of the pyramid 40. If it exists, a template for such a pyramid 40 should subdivide each of the four triangular faces 42 of the pyramid 40 into three smaller quadrilateral faces and the bottom quadrilateral face 44 into four smaller quadrilaterals. FIG. 5 illustrates a layout 50 depicting the all-quad division of the faces of the pyramid 40 in FIG. 4. Each all-quad element for a triangular face 42 is given by the reference numeral 52 and each all-quad element for the quadrilateral face 44 is given by the reference numeral 54. Given this boundary mesh consisting of 16 (sixteen) quadrilaterals, finding a valid internal structure that dices the pyramid into a set of smaller hex elements is difficult, and there is no valid solution published for this open problem as discussed in Schneiders, R., xe2x80x9cA grid-based algorithm for the generation of hexahedral element meshesxe2x80x9d, Engineering with Computers, 1996, 12, pp. 168-177, and as posted at http://www-users.informatik.rwth-aachen.de/xcx9croberts/open.html (hereafter collectively referred to as xe2x80x9cSchneidersxe2x80x9d). This problem is referred to as Schneiders"" Open Problem. Although a solution to the Schneiders"" problem is proposed in Carbonera, C.D., xe2x80x9cConstrained Mesh Generationxe2x80x9d, posted at http://www-users.informatik.rwth-aachen.de/xcx9croberts/SchPyr/index.html (hereafter xe2x80x9cCarboneraxe2x80x9d), this solution is not valid because some interior faces are not shared by two hexes.
FIG. 6 illustrates some examples of how a quadrilateral face 60 of a pyramid is split into rectangular patterns 62,64,66 and 68. The pattern 62 shows a 2xc3x972 split, the pattern 64 shows a 2xc3x971 split, the pattern 66 shows a 4xc3x972 split, and the pattern 68 shows a 4xc3x974 split. One known simple template for a pyramid is the one that first splits the pyramid into two tet elements and then applies the known tet template to each tet. FIG. 7 illustrates splitting of the bottom quadrilateral face 70 of a pyramid using the known tet template. With this template, the bottom quadrilateral face 70 is split into the 2xc3x972 triangular pattern 72. Other variations of the pattern 72 include the 4xc3x972 triangular pattern 74 and the 4xc3x974 triangular pattern 76.
If the bottom face of a pyramid is subdivided into a triangular pattern, however, a hex element or a prism element adjacent to the pyramid must have a triangular pattern on one face in order to maintain the interface conformity. This brings up another unsolved problem of finding conversion templates for a hex and a prism that have both rectangular patterns and triangular patterns mixed on the exterior surface of the hex and the prism. A partial solution to this problem is presented in Mitchell, S. A., xe2x80x9cThe All-Hex Geode-Template for Conforming a Diced Tetrahedral Mesh to any Diced Hexahedral Meshxe2x80x9d, Proceedings of 7th International Meshing Roundtable, 1998 (hereafter xe2x80x9cMitchellxe2x80x9d), the disclosure of which is incorporated herein by reference in its entirety. FIG. 8 illustrates the Geode template 80. The Geode template 80 has a top face 82, four side faces 86, and a bottom face 84. As illustrated in FIG. 8, the Geode template 80 has a triangular subdivision pattern on the top face 82, a rectangular subdivision pattern on the bottom face 84, and an irregular subdivision pattern on each side face 86. The irregular subdivision pattern limits the application and practical value of the Geode template 80.
In summary, there are two approaches to the all-hex conversion template, but no complete solution to these two approaches has been published: (1) to find a template for a pyramid that has a rectangular subdivision pattern on the bottom face, as pointed out in Schneiders, and (2) to find templates for a hex and a prism that have mixed subdivision patterns, rectangular and triangular, as pointed out in Mitchell.
There are several hex-meshing algorithms that are a variation of the advancing front method. Meyers presents an algorithm called plastering, which creates hex elements one by one by starting from domain boundaries and moving inward. Blacker and Tautges present a method called whisker weaving. The whisker weaving method creates a topology of a hex mesh first and then constructs the geometry of the mesh based on the topological information. Saigal presents an algorithm called H-Morph, which converts a tet mesh to a hex-dominant mesh by creating hex elements one by one starting from domain boundaries and moving inward. The method in Saigal is different from plastering in Meyers in that Saigal""s method starts with a tetrahedral mesh and always maintains a valid hex-tet mixed mesh during the process.
Schneiders presents an algorithm that creates a hex-mesh using an overlay grid. Schneiders"" method creates a structured grid that contains a target geometric domain and then converts all interior cells that are inside the domain into hex elements. After converting all interior cells into hex elements, the method subdivides cells that intersect a boundary into hex elements when it is possible. Finally, locations of the nodes that are close to the boundary are adjusted in order to conform the mesh to the target domain boundary. While the concept is straightforward, the robust implementation of this method for a complex geometric domain is difficult, and the final mesh has poor quality elements around the domain boundary, which is often the most critical part in engineering analysis.
An algorithm, called multisweep, is presented in Shepherd, J., et al., xe2x80x9cMethods for Multisweep Automationxe2x80x9d, Proceedings of 9th International Meshing Roundtable, 2000 (hereafter xe2x80x9cShepherdxe2x80x9d). Shepherd""s multisweep method creates hex elements by sweeping a quadrilateral mesh. When a target domain can be decomposed into sweepable sub-domains, the multisweep algorithm successfully creates an all-hex mesh. For a complex geometric domain, however, there is no guarantee that a target domain can be decomposed into sweepable sub-domains.
One practical alternative to all-hex meshing is hex-dominant meshing. A hex-dominant mesh is much easier to generate by hand or by an automatic method. For example, one could use the advancing front method or one of its variations to create hex elements near the domain boundary. For a remaining volume, one can fill non-hex elements, such as pyramids, prisms, and tets. Owen presents a method that places pyramids on the faces of the hex elements that are exposed to a remaining volume. After pyramids are placed, the remaining volume is enclosed only by triangles. The remaining volume is then filled with tet elements to yield a hex-dominant mesh.
Because it is much easier to create a quality hex-dominant mesh than a quality all-hex mesh, it is desirable to pursue a method for converting a hex-dominant mesh to an all-hex mesh. Mitchell proposes such a conversion method with the Geode template 80 mentioned hereinbefore with reference to FIG. 8. As noted hereinbefore, the Geode template 80 is an all-hex conversion template that has one triangular pattern on the top face 82, one rectangular pattern on the bottom face 84, and four irregular patterns on the side faces 86. When an advancing front method stops and leaves an unmeshed volume, a layer of Geode is laid on the boundary of the remaining volume. This has to be performed in such a way that a face on the Geode template with the rectangular pattern (e.g., the face 84 in FIG. 8) is shared with another hex created by the advancing front method and that a face on the Geode template with a triangular pattern (e.g., the face 82 in FIG. 8) is exposed to the remaining volume. In a way similar to Owen""s hex-dominant method, Mitchell""s method places tets on the triangular side of the Geode template. The remaining volume enclosed by triangles of the pyramids is also meshed into a set of tet elements. Finally tets are diced into hexes to complete a conversion of the input hex-dominant mesh to an all-hex mesh.
While Mitchell""s Geode template is a novel approach to the all-hex mesh conversion problem, it has a major limitation: because of the irregular subdivision pattern on its side faces, the Geode template is applicable only to a closed shell-like volume. Mitchell""s Geode tempalate would be more powerful and easier-to-use if the side faces had a rectangular pattern.
It is therefore desirable to provide a mesh conversion template that fully automates the conversion from a hex-dominant mesh to an all-hex mesh. It is also desirable to be able to freely combine triangular and rectangular patterns on the mesh conversion template""s exterior faces regardless of the type of the constituent element (i.e., a hex, a prism, a pyramid, or a tet) in the input hex-dominant mesh.
In one embodiment, the present invention contemplates a method to convert a hex-dominant mesh structure into an all-hex mesh structure, wherein the hex-dominant mesh structure includes at least one of the following constituent elements: one or more hexahedral elements, one or more prism elements, one or more pyramid elements, and one or more tetrahedral elements. The method comprises identifying a template shape corresponding to each constituent element in the hex-dominant mesh structure, wherein each template shape has the same number of external surfaces as in the corresponding constituent element; modularly constructing a plurality of sub-templates corresponding to each said template shape identified, wherein all sub-templates in the plurality of sub-templates, when assembled, produce a corresponding template shape identified, wherein each of the plurality of sub-templates is constituted of a plurality of hexahedral elements and supplies at least one of the external surfaces for the corresponding template shape, and wherein at least one of the external surfaces supplied by each of the plurality of sub-templates has a subdivision pattern selected from the group consisting of a rectangular subdivision pattern and a triangular subdivision pattern; assembling all sub-templates in the plurality of sub-templates to compose the corresponding template shape; and combining all template shapes composed by assembling corresponding sub-templates in the shape of the hex-dominant mesh structure, thereby generating the all-hex mesh structure for the hex-dominant mesh structure. The method to generate the all-hex mesh structure may be coded in software and executed on a computer. Furthermore, two or more sub-templates may be generated in parallel to reduce processing time and avoid any memory size restrictions.
In another embodiment, the present invention contemplates a method for providing a three-dimensional (3D) all-hex mesh for a geometric region. The method comprises receiving configuration data about the geometric region in a predetermined format (e.g., as a hex-dominant mesh structure) from a remote user over a communication network (e.g., the Internet); generating the 3D all-hex mesh for the geometric region using the configuration data in the predetermined format; and sending the 3D all-hex mesh to the remote user over the communication network.
The present invention describes a modular approach to designing all-hex mesh conversion templates where triangular and rectangular subdivision patterns may arbitrarily be combined on the exterior faces of the templates. The templates can be created for any arbitrary-shaped, complex geometric domain. The all-hex conversion software according to the present invention take as input any type of a hex-dominant mesh and converts it to an all-hex mesh automatically. An all-hex template according to the present invention is not a single specific template. Instead, it is a family of modular sub-templates. These sub-templates can be assembled to form all-hex conversion templates for hexes, pyramids, and prisms. There are two types of modular sub-templates according to the present invention, called a core and a cap. For a hex or prism element, one core is defined, which specifies the subdivision patterns of two faces of the input hex or prism. Then four caps are defined for a hex and three caps for a prism to specify the subdivision patterns of the other faces. One can mix and combine two subdivision patterns, rectangular and triangular, freely on the exterior surfaces of a hex, prism, and a pyramid.
The methodology of the present invention may be used in mesh generation for finite element analysis in any engineering field and also in other applications using 3D meshes, such as, for example, volume rendering in computer graphics. Using the modular approach of the present invention, a hex-dominant mesh can be converted into an all-hex mesh successfully without losing the mesh conformity. The methodology of the present invention can be applied to any hex-dominant mesh created by various hex-dominant meshing methods presently available. Furthermore, the all-hex conversion software according to the present invention allows easy detection if any all-hex templates are used or not. In other words, if an all-hex mesh is created using the conversion software of the present invention, then one can easily detect the all-hex templates by parsing the mesh.